// One constranint for Dijkstra's algorithm is
// that the graph must only contain non-negative edge weights.
// This constraint is imposed to ensure that once a node has been
// visited it's optimal distance cannot be improved.
// This is property is  especially important because it enables 
// Dijkstra's algorithm to act in greedy manner by always selecting
// the next most promising node

// constraint [n. 约束；限定]
// optimal [adj. 最佳的；最优的]
// promising [adj. 有希望的; 有前途的; 有出息的;]
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> II;

template <typename T>
void printVector(vector<T> nums)
{
    for (auto n : nums)
    {
        cout << n << ' ';
    }
    cout<<endl;
}


// Runs Dijkstra's algorithm and returns an array that contains
// the shortest distance to every node from the start node s.
// graph - neighbours of index node
// val - edges' weights of index node
// startNode - start node 
vector<int> lazyDijkstra(vector<vector<int>> graph, vector<vector<int>> val, int startNode){
    int numNodes = graph.size();
    auto func = [](II &A, II &B){return A.second > B.second;};
    priority_queue<II,vector<II>,decltype(func)> pq(func);
    vector<bool> visited(numNodes);
    vector<int> dist(numNodes, INT_MAX);
    dist[startNode] = 0;
    pq.push(II(startNode,0));

    while(!pq.empty()){
        II cur = pq.top();
        int node = cur.first;
        int nodeVal = cur.second;
        visited[node] = true;
        pq.pop();

        if(dist[node] < nodeVal) continue;
        else dist[node] = min(nodeVal,dist[node]);
        vector<int> neighbours = graph[node];
        vector<int> weights = val[node];
        for(int i = 0; i < neighbours.size(); i++){
            if(visited[neighbours[i]]) continue;
            pq.push(II(neighbours[i],weights[i]+nodeVal));
        }
    }

    return dist;
}

vector<int> EagerDijkstra(vector<vector<int>> graph, vector<vector<int>> val, int startNode){
    int numNodes = graph.size();
    auto func = [](II &A, II &B){return A.second > B.second;};
    priority_queue<II,vector<II>,decltype(func)> pq(func);
    vector<bool> visited(numNodes);
    vector<int> dist(numNodes, INT_MAX);
    dist[startNode] = 0;
    pq.push(II(startNode,0));

    while(!pq.empty()){
        II cur = pq.top();
        int node = cur.first;
        int nodeVal = cur.second;
        visited[node] = true;
        pq.pop();

        if(dist[node] < nodeVal) continue;
        else dist[node] = min(nodeVal,dist[node]);
        vector<int> neighbours = graph[node];
        vector<int> weights = val[node];
        for(int i = 0; i < neighbours.size(); i++){
            if(visited[neighbours[i]]) continue;
            pq.push(II(neighbours[i],weights[i]+nodeVal));
        }
    }

    return dist;
}



int main(){
    vector<vector<int>> graph = {
        {1,2},
        {3},
        {1,3},
        {4},
        {}
    };
    vector<vector<int>> val = {
        {4,1},
        {1},
        {2,5},
        {3},
        {}
    };
    printVector(lazyDijkstra(graph,val,1));
    return 0;
}